\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb,graphicx,url,charter,tikz}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.2in { {\bf CS390 Computational Game Theory and Mechanism Design}
     	 \hfill #2 }
       \vspace{4mm}
       \hbox to 6.2in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.2in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\handout}[3]{\heading{#1}{#2}{Feng Shi}{}{#3}}

\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}

\handout{1}{2013.7.9}{Problem Set 2}

\paragraph{Problem 1} (No collaborator.)
The normal-form game below has three players. Player 1 chooses rows, player 2 chooses columns, and 
player 3 chooses matrices. We only indicate player 3's utility. Show that action $D$ is not a best 
response for player 3 to any independent belief about his opponents' plays (i.e., mixed strategies 
		for players 1 and 2), but that $D$ is not strictly dominated.

\begin{center}
\begin{tabular}{c|c|c|}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $U$                  & 9                     & 0                      \\ [1ex] \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $D$                  & 0                     & 0                      \\ [1ex] \cline{2-3}
\multicolumn{3}{c}{}                                                  \\ [-2ex]
\multicolumn{1}{c}{} & \multicolumn{2}{c}{$A$} \\
\end{tabular}
$\quad\quad$
\begin{tabular}{c|c|c|}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $U$                  & 0                     & 9                      \\ [1ex] \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $D$                  & 9                     & 0                      \\ [1ex] \cline{2-3}
\multicolumn{3}{c}{}                                                  \\ [-2ex]
\multicolumn{1}{c}{} & \multicolumn{2}{c}{$B$} \\
\end{tabular}
$\quad\quad$
\begin{tabular}{c|c|c|}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $U$                  & 0                     & 0                      \\ [1ex] \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $D$                  & 0                     & 9                      \\ [1ex] \cline{2-3}
\multicolumn{3}{c}{}                                                  \\ [-2ex]
\multicolumn{1}{c}{} & \multicolumn{2}{c}{$C$} \\
\end{tabular}
$\quad\quad$
\begin{tabular}{c|c|c|}
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $U$                  & 6                     & 0                      \\ [1ex] \cline{2-3}
 & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
  $D$                  & 0                     & 6                      \\ [1ex] \cline{2-3}
\multicolumn{3}{c}{}                                                  \\ [-2ex]
\multicolumn{1}{c}{} & \multicolumn{2}{c}{$D$} \\
\end{tabular}
\end{center}

\textbf{Solution:}

In order for $D$ to be a best response fro player $3$ to any independent belief about his opponent's
plays, (use $U$, $L$, $D$, $R$ to indicate the probability of player $3$'s belief of other players )
$$\left\{ \begin{array}{l}
		6(UL+DR)\geq 9UL \\
		6(UL+DR)\geq 9DR \\
		6(UL+DR)\geq 9(UR+DL) \\
		U,R,D,L\geq 0\\
		U+D=L+R=1
	\end{array} \right.$$
We claim it has no solution. So we prove if $UL+DR\geq\frac{3}{2}UL$ and $UL+DR\geq\frac{3}{2}DR$\\
it must be $UL+DR<\frac{3}{2}(UR+DL)$.\\
By first two inequality we have $UL+DR<3 \ \min\lbrace UL,DR\rbrace$ so next prove 
$min\lbrace UL,DR\rbrace <\frac{1}{2} (UR+DL)$. This can be seen by 
$min\lbrace UL,DR\rbrace<\frac{1}{4}$.

Suppose $D$ is strictly dominated by some mixed strategy $s=aA+bB+cC+dD$, where $a,b,c,d\in [0,1]$ and $a+b+c+d=1$.
When player $1$ plays $U$ and player $2$ plays $L$ we have $9a+6d>6$.\\
When player $1$ plays $D$ and player $2$ plays $R$ we have $9c+6d>6$.\\
Combinning them yields $9a+9c+12d>12$ and with $a+c+d\leq 1$ thus $9\geq 9(a+c+d)$ we have
$d>1$, a contradiction. So $D$ is not strictly dominated.
\bigskip

\paragraph{Problem 2} (No collaborator.)
(OR94, Exercise 99.1.) Give an example of an infinite horizon game for which the one deviation 
property does not hold.

\textbf{Solution:}

%Infinite horizon games that are not continuous does not have one-deviation property.
%A infinite game is continuous if for each player $i$ the utility $u_i$ satisfies
%$$|u_i(h)-u_i(h')|\to 0 \ as \ t\to \infty \ where \ h_t=h_t'$$
Construct a single player game where at each step player has $2$ choices, choosing $a$
leads to a terminal state with utility $1$ and choosing $b$ leads to a same state. The only 
infinite history has utility $2$. Then choosing $a$ at each state satisfies all requirement
in one-deviation property except finite horizon, since choosing $b$ instead leads to non-terminal
thus yields no payoff. But choosing $a$ after any history is not a subgame perfect equilibrium
since choosing $b$ infinitely many times yields utility $2$. So the requirement that the game is
finite horizon is neccessary in one-deviation property.

%\begin{center}
%\begin{tikzpicture}
%[scale=.8,auto=left,every node/.style={circle,fill=blue!20}]
%  \node (n6) at (1,10) {6};
%  \node (n4) at (4,8)  {4};
%  \node (n5) at (8,9)  {5};
%  \node (n1) at (11,8) {1};
%  \node (n2) at (9,6)  {2};
%  \node (n3) at (5,5)  {3};

%  \foreach \from/\to in {n6/n4,n4/n5,n5/n1,n1/n2,n2/n5,n2/n3,n3/n4}
%    \draw (\from) -- (\to);
%\end{tikzpicture}
%\end{center}

\bigskip

\paragraph{Problem 3} (No collaborator.)
The Pirate game.

There are 5 rational pirates, $A, B, C, D$ and $E$. They find 100 gold coins. 
They must decide how to distribute them.
The pirates have a strict order of seniority: $A$ is superior to $B$, who is superior to $C$, 
	who is superior to $D$, who is superior to $E$.
The pirate world's rules of distribution are thus: that the most senior pirate should propose a 
distribution of coins. The pirates, including the proposer, then vote on whether to accept this 
distribution. If the proposed allocation is approved by a majority or a tie vote 
(e.g., 2 out of 4 approve), it happens. If not, the proposer is thrown overboard from the pirate 
ship and dies, and the next most senior pirate makes a new proposal to begin the system again.

The pirates' preferences about the outcomes are as follows. First of all, each pirate wants to 
survive (say being thrown overboard gives him utility $-\infty$). Second, given survival, 
each pirate wants to maximize the number of gold coins he receives. 
Third, each pirate would prefer to throw another overboard, if all other results would otherwise 
be equal (e.g., if $D$ can get 1 coin from either $B$ or $C$, he prefers to throw $B$ overboard and
		get the coin from $C$).
The pirates behave independently.

Solve this game using backward induction. What is the final distribution of the coins?

\textbf{Solution:}

\begin{enumerate}

\item[(1)] If pirate $E$ is to propose a division, that is, all others have been thrown,
he will take all the $100$ coins since he himself makes the majority.

\item[(2)] If pirate $D$ is to propose a division, he will also take all the $100$ coins
since he will at least get a tie in voting.

\item[(3)] If pirate $C$ is to propose a division, he needs either pirate $D$ or $E$ to vote
for him. So he can take $99$ coins and give pirate $E$ $1$ coin so that pirate $E$ will vote
for this division, because if he doesn't, pirate $D$ can vote against pirate $C$ and get all
the coins through strategy in $(2)$. \\
So the division given by pirate $C$ will be $(/,/,99,0,1)$.

\item[(4)] if the pirate $B$ is to propose a division, he only $1$ pirate among $C$ ,$D$ and $E$
to vote for him. He needs to pay at least $99$ coins to pirate $C$ to vote for him since pirate
$C$ can get $99$ coins by voting down. He needs only to pay $1$ coin to pirate $D$ since pirate
$D$ cannot receive any coin if pirate $C$ is to vote. \\
So the division given by pirate $B$ will be $(/,99,0,1,0)$.

\item[(5)] Back to the beginning, pirate $A$ is to propose a division. He needs $2$ other pirate
to vote for him among all others. Pirate $B$ will cost him at least $99$ coins, it's too much.
He can pay $1$ coin to pirate $C$ to get him to vote up since pirate $C$ cannot get a coin if
pirate $B$ is to propose a division. And he can pay $1$ coin to pirate $E$ for the same reason.\\
So the final division (given by pirate $A$) will be $(98,0,1,0,1)$.

\end{enumerate}

\bibliographystyle{agsm}

\begin{thebibliography}{99}

\bibitem{OR94}{M. J. Osborne and A. Rubinstein. {\em A course in game theory.} MIT Press, 1994.}

\bibitem{NRTV07}{N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds). 
	\\{\em Algorithmic game theory.} Cambridge University Press, 2007. }

\end{thebibliography}

\end{document}
